
\chapter{\label{sub:Finite-time-Consensus-on}Finite-time DAC on Generalized
Conditions }



It is shown in section \ref{sub:Find_Consensus_Value} that finite-time
DAC algorithm can calculate the consensus value by a linear combination
of local values in the past, if each node knows the network topology
(or eigenvalues of the weight matrix $W$). However, having knowledge
of the network topology in every node is a demanding assumption. Although
a distributed algorithm to calculate the linear combination has also
been introduced in \cite{Sundaram2007}, it requires several runs
of the consensus algorithm initialized with a set of linear independent
vectors. Alternatively, the original consensus algorithm can run many
instances in parallel with a set of independent initial values. However,
the data transmission at each iteration increases. Futhermore, this
method may not reliable to topology changes during the of multiple
re-initializations of original consensus algorithm. 

Here we propose a generalized finite-time DAC algorithm, which does
not require knowledge of network topology and re-initialization of
the original consensus algorithm for several times. In the future
research, the finite-time DAC algorithm probably will be generalized
to non-symmetrical network. Before introducing the algorithm, there
are too important linear filter need to be introduced, as the algorithm
is based on the properties of these filters. The first is the FIR
filter to estimate the consensus value which introduced in section
\ref{sub:Find_Consensus_Value}. The second is introduced in the next
section \ref{sec:Linear-Predictor-For}.


\section{\label{sec:Linear-Predictor-For}Linear Predictor For Local Value
}

In observing the convergence curve of each node's local value sequence,
we would come to the idea that the sequence must obeys some rule as
it converges. In section \ref{sub:Find_Consensus_Value}, it is shown
that local value vector can be decomposed in terms of eigenvalues
and eigenvectors. Based on this fact, a consensus value estimation
method by inverting the Vandermonde matrix  are proposed.

However, another important property of the FO-DCA need to be highlighted
in this section. To show this , we have the following theorem.
\begin{thm}
\label{thm:LV predictor a_i} For the DAC iteration $\mathbf{x}(k+1)=W\mathbf{x}(k)$
with $W$ satisfying the convergence condition in theorem \ref{thm:convergence condition}
, for any $k\geq m$ , where $m$ is a certain number, local value
\textup{$x_{i}\left(k\right)$} at node $v_{i}$ is equal to a linear
combination of local values of itself in $m$ previous time steps,
i.e. $x_{i}\left(k\right)=-a_{m-1}x_{i}\left(k-1\right)-\ldots-a_{1}x_{i}\left(k-m+1\right)-a_{0}x_{i}\left(k-m\right)$. \end{thm}
\begin{proof}
the minimal polynomial of $W$ is given by

\begin{eqnarray}
p(\lambda) & = & \prod_{i=1}^{r}\left(\lambda-\lambda_{i}\right)^{r_{i}}=0\nonumber \\
 & = & \lambda^{m}+a_{m-1}\lambda^{m-1}+\ldots+a_{1}\lambda+a_{0}\label{eq:polynomial of matrix W}
\end{eqnarray}
where $m=\sum_{i=1}^{r}r_{i}$. Since $p\left(W\right)=\mathbf{0}_{n\times n}$,
we have, 
\[
W^{m}+a_{m-1}W^{m-1}+\ldots+a_{1}W+a_{0}I=\mathbf{0}_{n\times n}
\]
multiplying both sides with $\mathbf{x}\left(0\right)$ we obtain
\begin{equation}
\mathbf{x}\left(k\right)+a_{m-1}\mathbf{x}\left(k-1\right)+\ldots+a_{0}\mathbf{x}\left(k-m\right)=\mathbf{0}_{n\times n}\label{eq:x(k+r) vector predictor}
\end{equation}
For any node $v_{i}\in{\cal V}$, its local value at time $k$ is
just the $i^{th}$ component of $\mathbf{x}\left(k\right)$. After
a little evolution, we have

\begin{equation}
x_{i}\left(k\right)=-a_{m-1}x_{i}\left(k-1\right)-\ldots-a_{0}x_{i}\left(k-m\right)\label{eq:x(k+r) predictor}
\end{equation}
In other words, $x_{i}\left(k\right)$ can be predicted by a FIR filter
given by $\left[-a_{r},-a_{r-1},\ldots,-a_{0}\right]$, if we pass
a number of consecutive local values in the past through that filter,
after the time index $k>m$. In addition, all the nodes in the network
can share the same coefficients, when the minimal polynomial of $W$
is not changed.\end{proof}
\begin{lem}
\label{lem:Sum-coef.=00003D1}The sum coefficients \textup{$\left\{ a_{j}\right\} =\left\{ a_{m-1},\ldots,a_{1},a_{0}\right\} $}
is equals to negative one, i.e. $\sum_{j=0}^{m-1}a_{j}=-1$\textup{. }\end{lem}
\begin{proof}
It is obvious when the iteration converges. Since Eq.\prettyref{eq:x(k+r) vector predictor}
satisfied as $k\to\infty$, we have $\bar{\mathbf{x}}+a_{m-1}\bar{\mathbf{x}}+\ldots+a_{1}\bar{\mathbf{x}}+a_{0}\bar{\mathbf{x}}=\mathbf{0}$.
Then, canceling the vector $\bar{\mathbf{x}}$ from the equation obtains
that the sum of all coefficients equals to negative one. 
\end{proof}
Given the local value vector sequence obtained by FO-DCA, one may
instantly comes to the idea of applying an adaptive filter algorithm
to estimate the set of coefficient. For example, LMS, LSL and Kalman
filter algorithms. One advantage of the adaptive filter algorithm
is that when the network topology is changed, the filter could adaptively
change its coefficient during the iteration. 


\subsection*{Find the Coefficients of Linear Predictor.}

After running FO-DAC algorithm for a number of step, node $v_{i}$
could list a number of equations by its available local values. Once
they are sufficient equations to construct a matrix, which is a Toeplitz
matrix, we can have a important result in the following.

Let  $T_{i}=T_{i}\left(k,D_{i}\right)\in\mathbb{R}^{D_{i}\times D_{i}}$
be a function at $v_{i}$ which outputs a Toeplitz matrix with size
$D_{i}$ with $x_{i}\left(k\right)$ as diagonal entries.

$T_{i}\left(k,D_{i}\right)=$ 
\begin{align}
\left[\begin{array}{cccc}
x_{i}\left(k\right) & x_{i}\left(k-1\right) & \ldots & x_{i}\left(k-D_{i}+1\right)\\
x_{i}\left(k+1\right) & x_{i}\left(k\right) & \cdots & x_{i}\left(k-D_{i}+2\right)\\
\vdots & \vdots & \ddots & \vdots\\
x_{i}\left(k+D_{i}-2\right) & x_{i}\left(k+D_{i}-3\right) & \cdots & x_{i}\left(k-2\right)\\
x_{i}\left(k+D_{i}-1\right) & x_{i}\left(k+D_{i}-2\right) & \cdots & x_{i}\left(k\right)
\end{array}\right]\label{eq:Toeplitz_i simple-1}
\end{align}
Similarly, Define the function $\mathbf{y}_{i}=\mathbf{y}_{i}\left(k,D_{i}\right)=\left[x_{i}\left(k+1\right),x_{i}\left(k+2\right),\ldots,x_{i}\left(k+D_{i}\right)\right]^{T}\in\mathbb{R}^{D_{i}}$
which outputs the local value history at $v_{i}$ from time $k+1$
to $k+D_{i}$.  Then, let $\mathbf{a}_{i}\left(D_{i}\right)=\left[a_{i,D_{i}-1},\ldots,a_{i,1},a_{i,0}\right]^{T}\in\mathbb{R}^{D_{i}}$
be a vector of length $D_{i}$ representing the coefficients in the
minimal polynomial calculated at $v_{i}$. Then, we have the solution
of these equations given by

\begin{equation}
\mathbf{a}_{i}\left(D_{i}\right)=-T_{i}^{-1}\left(k,D_{i}\right)\mathbf{y}_{i}\left(k,D_{i}\right)\label{eq:Toeplitz Eq.-2}
\end{equation}
The size of the Toeplitz block $D_{i}$, should be less or equal to
$m$ so that the Eq.\prettyref{eq:Toeplitz Eq.-2} have unique solution.
To solve Eq.\prettyref{eq:Toeplitz Eq.-2}, node $i$ need to have sufficient
local values.

Toeplitz matrix is a special type of matrix and can be inverted by
some algorithms in the polynomial time of order $D_{i}^{2}$, rather
than the order of $D_{i}^{3}$ in general case (for example by LU
decomposition), which is an enormous computational saving \cite{Prass2007}.
Levinson developed a recursive algorithm to solve the system quickly
if the Toeplitz matrix is symmetric. 

One interesting advantage of Levinson's method is it can also apply
to the case when weight matrix is non-symmetric. The fact that the
method can be generalized to the non-symmetric case is stated in the
texts \cite{Robinson2000}.  Therefore, We will invert this Toeplitz
matrix using Levinson's method. The proposed method  doesn't need
to be changed and can generalize to the non-symmetric weight matrix
case. 

It totally needs $2r+2$ local values and $2r+1$ iterations to construct
the Toeplitz matrix and Eq.\prettyref{eq:Toeplitz Eq.-2}, but all the local
value can be obtained from one instance of FO-DCA. In contract, the
the original finite-time consensus algorithm in \cite{Sundaram2007}
requires $r$ iterations of FO-DCA for each instance, and totally
$r$ instances. Therefore, the proposed method has some improvement
to the original finite-time consensus algorithm. 

In the next section \ref{sub:Convert-Linear-Predictor }, we will
show how to obtain the consensus finding filter by linear predictor
coefficients.


\section{\label{sub:Convert-Linear-Predictor }Convert Linear Predictor To
Consensus Finding Filter}

Once there are sufficient local values, node $i$ can solve the equation
and obtain the set of coefficients \textbf{$\mathbf{a}$} and construct
the polynomial 
\[
p(\lambda)=\lambda^{m}+a_{m-1}\lambda^{m-1}+\ldots+a_{1}\lambda+a_{0}
\]


If matrix $W$ satisfies the condition in \prettyref{thm:convergence condition}
there is a simple eigenvalue equals to one. As shown in section \ref{sub:Find_Consensus_Value},
the consensus finding filter is given by the row of inverse of Vandermonde's
matrix which corresponding to an eigenvalue equals to one. Without
loss of generality, let the first eigenvalue $\lambda_{1}=1$. Thus,
the consensus finding filter is given by the first row of the inverse
of Vandermonde's Matrix.

Examining the the Lagrange's polynomial interpolation formula \prettyref{eq:Lagrange's polynomial}
we can rewrite the consensus finding filter in terms of $a_{k}$. 

To make the expression simple, we may define another polynomial (Also
see Eq.\prettyref{eq:intermindia polynomial})

\[
q\left(\lambda\right)=\frac{p\left(\lambda\right)}{\lambda-1}=c_{m}\lambda^{m-1}+c_{m-1}\lambda^{m-2}+\ldots+c_{2}\lambda+c_{1}
\]
where $c_{k}=1+\sum_{j=k+1}^{m}a_{j}$. The consensus finding filter
can be given by the coefficient in $q\left(\lambda\right)$. 
\begin{equation}
\mathbf{h}=\frac{\left[c_{m},c_{m-1},\ldots,c_{2}\right]}{\sum_{k=1}^{m}c_{k}}\label{eq:Consensus Filter by polynomial}
\end{equation}
This indicates the possibility of using the adaptive filter to estimate
the consensus value after a certain number of iterations. 

One interesting property of the consensus finding filter is that it
can be found by this method when the weight matrix is non-symmetric.
It can be demonstrated by finding the inverse of a confluent Vandermonde
matrix. In examining the expression of the inverse of confluent Vandermonde
matrix, we note that the row corresponding to the unity eigenvalue,
can actually the coefficients of a consensus finding filter. The the
length of the filter is not required to be the same. It may be not
equal to the number of distinct and nonzero eigenvalues $m$, but
equal to the sum of all orders in minimal polynomial of weight matrix
$\sum_{i=1}^{m}r_{i}$. However, the relationship of local value predictor
and consensus finding filter still holds. 


\section{Simulation\label{sub:Numerical-Simulation}}

\begin{figure}
\hfill{}\includegraphics{\string"Graph/Report_DAC/Net_Weight/graph with 8 nodes and 17 edges\string".pdf}\hfill{}\hfill{}\caption{\label{fig:Graph in Xiao'paper}Graph with optimal weights which maximize
convergence rate }
\end{figure}


Consider the graph from \cite{Xiao2004}, the weight matrix \textbf{$W$}
corresponding to this graph is symmetric and has eigenvalues $\lambda(W)=\{1,0.6,0.4,0,0,0,-0.4,-0.6\}$.
The time index $k$ can be chosen large enough so that there are surfficient
number of local values to estimate the filter coefficients.  For example,
there are 5 distinct and nonzero eigenvalues of \textbf{$W$}, so
we choose the time index $k=5$ and $d=5$ which is the minimum filter
length.

 Based on Eq.\prettyref{eq:Consensus Filter by polynomial}  the consensus
finding filter is given by

\[
\mathbf{h}=\left[1.8601,\;0,\;-0.9673,\;0,\;0.1071\right]^{\mathrm{T}}
\]


\begin{figure}
\hfill{}\includegraphics[width=8cm]{\string"Graph/Report_DAC/MSE/MSE_Filter vs FODAC\string".pdf}\hfill{}

\caption{\label{cap:perform. Consensus Filter}Performance of the first order
iteration with optimal matrix vs. consensus finding filter algorithm}
\end{figure}


For any random generated $\mathbf{x}(0)\in R^{n}$, node values vector
$\mathbf{x}(k)$ is updated by the iteration Eq.\prettyref{eq:first order matrix}.
At the same time each node passes its local values though filter $\mathbf{h}$.
Filter output is given by $\hat{x}_{i}(k)=\mathbf{h}(k)*x_{i}(k)$.
Fig.\ref{cap:perform. Consensus Filter} compares the first order
DAC (FO-DAC) algorithm with optimal matrix and the proposed algorithm
with consensus finding filter. The performance is evaluated by the
mean square error (MSE), defined by $\mbox{MSE}_{\mbox{FO-DAC}}(k)=\sum_{i\in\mathcal{N}}E[\left|x_{i}(k)-\bar{x}\right|^{2}]$,
$\mbox{MSE}_{\mbox{filter}}(k)=\sum_{i\in\mathcal{N}}E[\left|\alpha_{i}(k)-\bar{x}\right|^{2}]$
respectively, where $\bar{x}=(1/n)\sum_{i\in\mathcal{N}}x_{i}(0)$.
The result shows that the consensus finding filter calculate the consensus
value after a finite number of iteration and MSE drops dramatically
to the quantization error at the same time. 


\section{Conclusion}

In this section, we introduced the finite-time DAC on gernerlized
condition. Compared to the previous version of finite-time DAC, the
improvements are: it doesn't require the eigenvalues to be known prior
to the algorithm. However, the number of iterations can not be less
than a certain limit, because the minimum number of iterations is
depends on the weight matrix, which is the same as the previous finite-time
DAC. With this improment, some further algorithm could be drived.
They will be introduced in chapter \ref{sec:Online-Optimization-of}.
